package algorithm.ldk.SelectionSort;

/**
 * @作者：ldk
 * @email 2505496685@qq.com
 * @描述：默认描述
 * @创建时间：9:54 2021-01-03
 * @修改时间：9:54 2021-01-03
 * @修改描述：默认描述
 */

import java.util.Arrays;
import java.util.Collections;

/**
 * 选择排序法
 */
public class SelectionSort {

    private  SelectionSort(){}

    public static  <E extends Comparable<E>> void sort(E[] arr){
        //arr[0...i)是有序的；arr[i...n)是无序的
        for(int i = 0; i < arr.length; i++){
            //选择arr[i...n]中的最小值的索引
            int minIndex = i;
            for(int j = i; j < arr.length; j ++){
                if(arr[j].compareTo(arr[minIndex]) < 0){
                    minIndex = j;
                }
            }

//            Collections.swap(Arrays.asList(arr),i,minIndex);
            swap(arr, i, minIndex);
        }
    }
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static  <E extends Comparable<E>> void sort2(E[] arr){
        //arr[i...n)是有序的；arr[0...i)是无序的
        for(int i = arr.length - 1; i >= 0; i--){
            //选择arr[i...n]中的最大值的索引
            int minIndex = i;
            for(int j = i; j >= 0; j --){
                if(arr[j].compareTo(arr[minIndex]) > 0) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }



    public static void main(String[] args) {

//        int n = 10000;

        int[] dataSize = {10000, 100000};
        for (int n : dataSize) {
            Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
            SortingHelper.sortTest("SelectionSort",arr);
        }

//        long startTime = System.nanoTime();
//        SelectionSort.sort(arr);
//        long endTime = System.nanoTime();
//
//        double time = (endTime - startTime) / 1000000000.0;
//
//        if(!SortingHelper.isSorted(arr)){
//            throw new RuntimeException("SelectionSort failed");
//        }
//        System.out.println(time);


//        Integer[] arr = {1,4,2,3,6,5};
//        SelectionSort.sort(arr);
//        for(int e : arr){
//            System.out.print(e + " ");
//        }
//        System.out.println();
//
//        Student[] students = {new Student("ldk",99),
//                                new Student("ldd",100),
//                                new Student("kqq",100)};
//
//        SelectionSort.sort(students);
//        for (Student student : students) {
//            System.out.print(student + " ");
//        }
//        System.out.println();
    }

}
